//集合里的数字有重复的，可以重复使用，但不能出现重复组合
//在搜索中去掉重复组合，一种是同一树枝上去重，一种是同一树层去重
//本题应该是同一树层，因为数层上的是不同组合，而树枝上的是同一组合
//去重要先给数组排序，
//若第一个选了元素x，那下一个如果也是元素x就不要再选了，因为无论后面有没有元素x，第一个选元素x时都包含了后面有0-n个元素x的情况
#include <vector>
#include <algorithm>
using std::sort;
using std::vector;
//1. 使用一个used数组来记录，若使用了则记为1，未使用则记为0；若i和i-1位的相同且i-1没有被使用，则说明i-1在树层的前一个树枝上有使用了，这一条数组就不要使用了，跳过循环直到遇到不同元素
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& candidates,int target,vector<bool>& used,int sum,int startIndex){
    if(sum==target){
        result.push_back(path);
        return;
    }
                                            //剪枝操作
    for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){
                 //去重操作
        if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false) continue;
        //如果used[i-1]==true，则说明同一树枝使用过candidate[i-1];
        //如果used[i-1]==false，则说明同一树层使用过candidate[i-1];


        sum+=candidates[i];
        path.push_back(candidates[i]);
        used[i]=true;                         //不重复使用相同（位置也相同的）元素，则用i+1
        backtracking(candidates,target,used,sum,i+1);
        //回溯
        used[i]=false;
        path.pop_back();
        sum-=candidates[i];
    }
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<bool> used(candidates.size());
    sort(candidates.begin(),candidates.end());  //排序
    backtracking(candidates,target,used,0,0);
    return result;

}




//使用startIndex去重，遇到相同的跳过即可
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& candidates,int target,int sum,int startIndex){
    if(sum==target){
        result.push_back(path);
        return;
    }
    for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){
        //去重条件      大于startIndex而不是大于等于是因为在sI可以取一个，递归也只取一次，最后保证只有一条树枝有重复的元素
        if(i>startIndex&&candidates[i]==candidates[i-1]) continue;
        //重复选择同一个元素的任务由第一条取到该元素的树枝完成
        sum+=candidates[i];
        path.push_back(candidates[i]);
        backtracking(candidates,target,sum,i+1);
        path.pop_back();
        sum-=candidates[i];
    }
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    if(!candidates.size()) return result;
    sort(candidates.begin(),candidates.end());
    backtracking(candidates,target,0,0);
    return result;

}